// KD树结点
class KDNode{
  constructor(dom_elt, split, left, right){
    this.dom_elt = dom_elt;
    this.split   = split;
    this.left    = left;
    this.right   = right;

    this.sMin    = 0;
    this.sMax    = 0;
  }

  // 获取KD树深度
  getDepth(){
    this.depth = 1;
    this.updateDepth(this, 1);
    return this.depth;
  }
  
  updateDepth(node, lv){
    if(!node) return;
    this.depth = Math.max(this.depth, lv);
    if(node.left){
      this.updateDepth(node.left, lv+1);
    }
    if(node.right){
      this.updateDepth(node.right, lv+1);
    }
  }

  name(){
    if(!this.dom_elt) return '';
    let str = '(';
    for(let i=0,il=this.dom_elt.length;i<il;i++){
      str += parseInt(this.dom_elt[i]);
      if(i !== il - 1){
        str += ',';
      }
    }
    str += ')';
    return str;
  }
  
  createChildren(root){
    if(root.left){
      let node = root.left
      let left = new KDNode(node.dom_elt, node.split, node.left, node.right);
      root.left = left;
      this.createChildren(root.left);
    }
    if(root.right){
      let node = root.right
      let right = new KDNode(node.dom_elt, node.split, node.left, node.right);
      root.right = right;
      this.createChildren(root.right);
    }
  }

  copyFromJSON(json){
    this.dom_elt = json.dom_elt;
    this.split   = json.split;
    this.left    = json.left;
    this.right   = json.right;

    this.createChildren(this);
  }
}

function createKDNode(split, data_set, dim=2){

  if(data_set.length <= 0) return;
  data_set.sort(function(a,b){ return a[split] - b[split];});
  var split_pos = Math.floor(data_set.length / 2);
  var median    = data_set[split_pos];
  var split_next = ( split + 1 ) % dim;

  let node =  new KDNode(
    median, 
    split, 
    createKDNode(split_next, data_set.slice(0, split_pos)),
    createKDNode(split_next, data_set.slice(split_pos + 1))
  );

  return node;
}

class NodeRange extends Array{
  constructor(props=2){
    super();
    if(props instanceof Number){
      for(var i=0; i < props; i++){
        this.push([0,0]);
      }
    }
    else if(props instanceof Array){
      for(let i=0, il=props.length; i < il; i++){
        const dat = props[i];
        this.push([0,0]);
        this[i][0] = dat[0];
        this[i][1] = dat[1];
      }
    }
  }
}

function calcNodeRange(node, range){
  if(!node || !node.dom_elt) return;

  const dom_elt = node.dom_elt;

  node.sMin = range[node.split][0];
  node.sMax = range[node.split][1];

  if(node.left){
    var leftRange = new NodeRange(range);
    leftRange[node.left.split][1] = dom_elt[node.split];
    calcNodeRange(node.left, leftRange);
  }

  if(node.right){
    let rightRange = new NodeRange(range);
    rightRange[node.right.split][0] = dom_elt[node.split];
    calcNodeRange(node.right, rightRange);
  }
}

export {KDNode, NodeRange, createKDNode, calcNodeRange};